Section: New Results

Theoretical and Methodological Developments

Participants : Andrew Miller, Arnaud Pêcher, Pierre Pesneau, Ruslan Sadykov, Gautier Stauffer, François Vanderbeck.

We made progress in the development of theory and algorithms in the area of “Reformulation and Decomposition Approaches for MIP”, “Mixed Integer Nonlinear Programming”, and “Polyhedral Combinatorics and Graph Theory”.

Column Generation for Extended Formulations

Working in an extended variable space allows one to develop tight reformulations for mixed integer programs. However, the size of the extended formulation grows rapidly too large for a direct treatment by a MIP-solver. Then, one can work with inner approximations defined and improved by generating dynamically variables and constraints. The alternative considered in [21] is an inner approximation obtained by generating dynamically the variables of the extended formulation. It assumes that the extended formulation stems from a decomposition principle. Then one can implement column generation for the extended formulation using Dantzig-Wolfe decomposition paradigm. Pricing subproblem solutions are expressed in the variables of the extended formulation and added to the current restricted version of the extended formulation along with the subproblem constraints that are active for the subproblem solutions.

Our paper [21] revisits the column-and-row generation approach, which is viewed herein as a generalization of standard column generation, the latter being based on a specific subproblem extended formulation. This generic view not only highlights the scope of applicability of the method, but it also leads to a more general termination condition than the traditional reduced cost criteria and to theoretically stronger dual bounds. We highlight a key benefit of the latter: lifting pricing problem solutions in the space of the extended formulation permits their recombination into new subproblem solutions and results in faster convergence.

The interest of the approach is evaluated numerically on machine scheduling, bin packing, generalized assignment, and multi-echelon lot-sizing problems. We compare a direct handling of the extended formulation, a standard column generation approach, and the “column-and-row generation” procedure. The results illustrate the stabilization effect resulting from column disaggregation and recombinations that is shown to have a cumulative effect when used in combination with a standard stabilization technique.

Primal Heuristics for Branch-and-Price

Primal heuristics have become an essential component in mixed integer programming (MIP). Generic heuristic paradigms of the literature remain to be extended to the context of a column generation solution approach. Our goal is to derive black-box primal heuristics for use in Branch-and-Price approaches. This requires extending primal heuristic paradigms to the context of dynamic generation of the variables of the model. We highlight an important fact: such generic tools typically performs better than problem specific meta-heuristics, in terms of solution quality and computing times. Based on our application specific experience with these techniques [55] , [57] , [72] , [73] , and on a review of generic classes of column generation based primal heuristics, in [49] , we are developing a full blown review of such techniques, completed with new methods and an extensive numerical study. This research is being carried on in collaboration with the members of the associated team project, SAMBA [27] [30] .

As a Dantzig-Wolfe reformulation is typically tighter than the original compact formulation, techniques based on rounding its linear programming solution have better chance to yield good primal solutions. The aggregated information built into the column definition and the price coordination mechanism provide a global view at the solution space that may be lacking in somewhat more “myopic” approaches based on compact formulations. However, the dynamic generation of variables requires specific adaptation of heuristic paradigms. Our contribution [30] lies in proposing simple strategies to get around these technical issues. We initially concentrate on “diving” methods and consider their combination with “sub-MIPing”, relaxation induced neighborhood search, truncated backtracking using a Limited Discrepancy Search. These add-ons serves as local-search or diversification/intensification mechanisms. The methods are numerically tested on standard models such as Cutting Stock, Vertex Coloring, Generalized Assignment, Lot-Sizing, and Vehicle Routing problems. We further extend this research by combining the “diving” method mentioned above with the “feasibility pump” approach [27] . We show how this combination can be implemented in a context of dynamically defined variables, and we report on numerically testing “feasibility pump” for cutting stock and generalized assignment problems.

Stabilization techniques for column generation

Within the SAMBA project, we are collaboratively studying techniques to accelerate the convergence of column generation algorithms [25] . This techniques exploit Lagrangian duality theory. By revisiting all the alternative approaches to solving the Lagrangian dual, we identify suitable combinations of paradigms.

We also bridge the gap with techniques used in the dual framework of cut generation that have their unexploited counterpart for column generation [32] , [29] . Cutting plane algorithmic strategies translate into stabilization procedures for column generation. We establish the link between the in-out separation procedure and dual price smoothing techniques for column generation. In this framework, we develop generic convergence proofs and effective smoothing auto-regulating strategies that avoids the need for parameter tuning. We further improve performance of such stabilization by hybridization with an ascent method. This work might inspire novel cut separation strategies.

Stable sets in claw-free graphs

A stable set is a set of pairwise non adjacent vertices in a graph and a graph is claw-free when no vertex contains a stable set of size three in its neighborhood. Given weights on the vertices, the stable set problem (a NP-hard problem in general) consists in selecting a set of pairwise non adjacent vertices maximizing the sum of the selected weights. The stable set problem in claw-free graphs is a fundamental generalization of the classic matching problem that was shown to be polynomial by Minty in 1980 (G. Minty. On maximal independent sets of vertices in claw-free graphs. J. Combinatorial Theory B, 28:284-304 (1980)). However, in contrast with matching, the polyhedral structure (i.e. the integer hull of all stable sets in a claw-free graph) is not very well understood and thus providing a `decent' linear description of this polytope has thus been a major open problem in our field.

We proposed a new algorithm to find a maximum weighted stable set in a claw-free graph [38] whose complexity is now drastically better than the original algorithm by Minty ($n^3$ versus $n^6$, where $n$ is the number of vertices). We also provided a description of the polyhedra in an extended space (i.e. using additional artificial variables) and an efficient procedure to separate over the polytope in polynomial-time [26] . Beside those main contributions, we published another papers on the strongly minimal facets of the polytope.

The Circular-Chromatic number

Another central contribution of our team concerns the chromatic number of a graph (the minimum number of independent stable sets needed to cover the graph). We proved that the chromatic number and the clique number of some superclasses of perfect graphs is computable in polynomial time [17] .

We investigated the circular-chromatic number. It is a well-studied refinement of the chromatic number of a graph (designed for problems with periodic solutions): the chromatic number of a graph is the integer ceiling of its circular-chromatic number. Xuding Zhu noticed in 2000 that circular cliques are the relevant circular counterpart of cliques, with respect to the circular chromatic number, thereby introducing circular-perfect graphs, a super-class of perfect graphs.

We proved that the clique and chromatic numbers of circular-perfect graphs is computable in polynomial time [16] , thereby extending Grötschel, Lovász and Schrijver's result to the whole family of circular-perfect graphs. We gave closed formulas for the Lovász Theta number of circular-cliques (previously, closed formulas were known for circular-cliques with clique number at most 3 only), and derived from them that the circular-chromatic number of circular-perfect graphs is computable in polynomial time [24] .